package twoSum;

import java.util.*;

public class Solution {
      public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
      class ListNode {
      int val;
      ListNode next;
      ListNode(int x) {
          val = x;
          next = null;
      }
  }
    public int[] twoSum(int[] nums, int target) {
        // 两数之和
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(target-nums[i])) {
                return new int[]{map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return null;
    }
    public int romanToInt(String s) {
        HashMap<Character,Integer>map=new HashMap<>();
        map.put('M',1000);
        map.put('D',500);
        map.put('C',100);
        map.put('L',50);
        map.put('X',10);
        map.put('V',5);
        map.put('I',1);
        int res=0;
        int last=0;
        for (int i = s.length()-1; i>=0; i--) {
            int v= map.get(s.charAt(i));//得到第i个位置的罗马字母的值，如果这个值小于上一次的值，就减去，否则加
            if(v<last){
                res-=v;
            }else{
                res+=v;
            }
            last=v;
        }
        return res;
    }
    public boolean hasCycle(ListNode head) {
          ListNode p = head;
        Set<ListNode> set = new HashSet<>();
        while (p!=null){
            if(set.contains(p)){
                return true;
            }
            set.add(p);
            p = p.next;
        }
        return false;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
          ListNode p1 = headA;
          ListNode p2 = headB;
          Set<ListNode> set = new HashSet<>();
          while (p1!=null){
              set.add(p1);
              p1 = p1.next;
          }
          while (p2!=null){
              if(set.contains(p2)){
                  return p2;
              }
              p2 = p2.next;
          }
          return null;
    }
    public int majorityElement(int[] nums) {
          //
//        Map<Integer,Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
//            if(map.get(nums[i])>nums.length/2){
//                return nums[i];
//            }
//        }
//        return 0;

        // 摩尔投票
//        int ans = nums[0];
//        int count = 1;
//        for (int i = 1; i < nums.length; i++) {
//            count+=(nums[i]==ans?1:-1);
//            if(count == 0){
//                ans = nums[i];
//                count = 1;
//            }
//        }
//        return ans;
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
    private int getNext(int n) {
        int totalSum = 0;
        while (n > 0) {
            int d = n % 10;
            n = n / 10;
            totalSum += d * d;
        }
        return totalSum;
    }
    public boolean isHappy(int n) {
        Set<Integer> seen = new HashSet<>();
        while (n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s2t = new HashMap<Character, Character>();
        Map<Character, Character> t2s = new HashMap<Character, Character>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }
    public boolean containsDuplicate(int[] nums) {
          Set<Integer> set = new HashSet<>();
          for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])){
                return true;
            }
            set.add(nums[i]);
          }
          return false;
    }
    public boolean containsNearbyDuplicate(int[] nums, int k) {
          // 滑窗 + 哈希
         // 直接判断在k的范围内有无相同数
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])){
                return true;
            }
            set.add(nums[i]);
            if(set.size()>k){
                set.remove(nums[i-k]);
            }
        }
        return false;
    }
    public int missingNumber(int[] nums) {
//          Set<Integer> set = new HashSet<>();
//        for (int i = 0; i < nums.length; i++) {
//            set.add(nums[i]);
//        }
//        for (int i = 0; i <= nums.length; i++) {
//            if(!set.contains(i)){
//                return i;
//            }
//        }
//        return 0;
        int n = nums.length;
        return (n+1)*n/2- Arrays.stream(nums).sum();
    }
    public int[] intersection(int[] nums1, int[] nums2) {
//          Set<Integer> set = new HashSet<>();
//          for (int i = 0; i < nums1.length; i++) {
//            set.add(nums1[i]);
//          }
//          Set<Integer> set1 = new HashSet<>();
//        for (int i = 0; i < nums2.length; i++) {
//            if(set.contains(nums2[i])){
//                set1.add(nums2[i]);
//            }
//        }
//        int[] ans = new int[set1.size()];
//        int i = 0;
//        for (int v: set1) {
//            ans[i++] = v;
//        }
//        return ans;

        // 双指针排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0,j = 0;
        Set<Integer> set = new HashSet<>();
        while (i<nums1.length&&j<nums2.length){
            if(nums1[i]<nums2[j]){
                i++;
            } else if (nums1[i]>nums2[j]){
                j++;
            } else {
                set.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] ans = new int[set.size()];
        int t = 0;
        for (int v: set) {
            ans[t++] = v;
        }
        return ans;
    }
    public int[] intersect(int[] nums1, int[] nums2) {
          // 返回出现次数小的那一组
//        Arrays.sort(nums1);
//        Arrays.sort(nums2);
//        int[] ans = new int[nums1.length+nums2.length];
//        int i = 0,j = 0,index = 0;
//        while (i<nums1.length&&j<nums2.length){
//            if(nums1[i]<nums2[j]){
//                i++;
//            } else if (nums1[i]>nums2[j]) {
//                j++;
//            } else {
//                ans[index++] = nums1[i];
//                i++;
//                j++;
//            }
//        }
//        return Arrays.copyOfRange(ans,0,index);

        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        int[] intersection = new int[nums1.length];
        int index = 0;
        for (int num : nums2) {
            int count = map.getOrDefault(num, 0);
            if (count > 0) {
                intersection[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
    }
    public boolean canConstruct(String ransomNote, String magazine) {
          int[] cnt = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            cnt[magazine.charAt(i)-'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            cnt[ransomNote.charAt(i)-'a']--;
            if(cnt[ransomNote.charAt(i)-'a']<0)return false;
        }
        return true;
    }
    public int firstUniqChar(String s) {
        int[][] map = new int[26][2];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map[c-'a'][1]++;
            map[c-'a'][0] = i;
        }
        int ans = -1;
        for (int i = 0; i < map.length; i++) {
            if(map[i][1] == 1) {
                if(ans == -1) ans = map[i][0];
                else ans = Math.min(ans,map[i][0]);
            }
        }
        return ans;
    }
    public List<Integer> findDisappearedNumbers(int[] nums) {
          Set<Integer> set = new HashSet<>();
        for (int i = 1; i <= nums.length; i++) {
            set.add(i);
        }
        for (int i = 0; i < nums.length; i++) {
            set.remove(nums[i]);
        }
        List<Integer> list = new ArrayList<>();
        for (int v: set) {
            list.add(v);
        }
        return list;
    }
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
          // 单调栈
        Map<Integer,Integer> map = help(nums2);
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = map.getOrDefault(nums1[i],-1);
        }
        return ans;
    }
    private Map<Integer,Integer> help(int[] nums){
          Stack<Integer> stack = new Stack<>();
          Map<Integer,Integer> map = new HashMap<>();
          for (int i = 0; i < nums.length; i++) {
             while(!stack.isEmpty()&&nums[stack.peek()]<nums[i]){
                map.put(nums[stack.pop()],nums[i]);
             }
            stack.push(i);
          }
          return map;
    }
    public int distributeCandies(int[] candyType) {
          // 贪心
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < candyType.length; i++) {
            set.add(candyType[i]);
        }
        return Math.min(set.size(),candyType.length);
    }
    public int findLHS(int[] nums) {
          // 最长和谐子序列
          // 可以选可以不选
          // 最大值和最小值的差值是1
          // 也就是 相同的数
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);
        }
        int ans = 0;
        for (int key: map.keySet()) {
            if(map.containsKey(key-1)) {
                ans = Math.max(ans,map.get(key-1)+map.get(key));
            }
        }
        return ans;
//        Arrays.sort(nums);
//        int begin = 0;
//        int res = 0;
//        for (int end = 0; end < nums.length; end++) {
//            while (nums[end] - nums[begin] > 1) {
//                begin++;
//            }
//            if (nums[end] - nums[begin] == 1) {
//                res = Math.max(res, end - begin + 1);
//            }
//        }
//        return res;
    }
    public String[] findRestaurant(String[] list1, String[] list2) {
          // 最小的索引 共同喜欢的餐厅
        Map<String,Integer> map = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            map.put(list1[i],i);
        }
        List<String> list = new ArrayList<>();
        int indexSum = Integer.MAX_VALUE;
        for (int i = 0; i < list2.length; i++) {
            if(map.containsKey(list2[i])) {
                if(indexSum>i+map.get(list2[i])){
                    indexSum = i + map.get(list2[i]);
                    list.clear();
                    list.add(list2[i]);
                } else if (indexSum == map.get(list2[i])+i) {
                    list.add(list2[i]);
                }
            }
        }
        return list.toArray(new String[list.size()]);
    }
    public int[] findErrorNums(int[] nums) {
          int n = nums.length;
          Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(!set.add(nums[i])){
                return new int[]{nums[i],(n*(n+1)/2-(Arrays.stream(nums).sum()-nums[i]))};
            }
        }
        return null;
    }
    public int findShortestSubArray(int[] nums) {
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i])[0]++;
                map.get(nums[i])[2] = i;
            } else {
                map.put(nums[i], new int[]{1, i, i});
            }
        }
        int maxNum = 0, minLen = 0;
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            int[] arr = entry.getValue();
            if (maxNum < arr[0]) {
                maxNum = arr[0];
                minLen = arr[2] - arr[1] + 1;
            } else if (maxNum == arr[0]) {
                if (minLen > arr[2] - arr[1] + 1) {
                    minLen = arr[2] - arr[1] + 1;
                }
            }
        }
        return minLen;
    }
    public boolean findTarget(TreeNode root, int k) {
//          return dfs(root,k,new HashSet<>());
        Deque<TreeNode> deque = new ArrayDeque<>();
        Set<Integer> set = new HashSet<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            if(set.contains(k-deque.peek().val)) {
                return true;
            }
            if(deque.peek().left!=null){
                deque.offer(deque.peek().left);
            }
            if(deque.peek().right!=null){
                deque.offer(deque.peek().right);
            }
            set.add(deque.poll().val);
        }
        return false;
    }
//    private boolean dfs(TreeNode root,int k,Set<Integer> set) {
//          if ( root == null ) {
//              return false;
//          }
//          if(set.contains(k-root.val)) {
//              return true;
//          }
//          set.add(root.val);
//          return dfs(root.left,k,set)||dfs(root.right,k,set);
//    }
    public int numJewelsInStones(String jewels, String stones) {
          int ans = 0;
        for (int i = 0; i < stones.length(); i++) {
            if(jewels.contains(stones.charAt(i)+"")){
                ans++;
            }
        }
        return ans;
    }
}
